// sgu300
//
// this is an O(n log n)'s method, but bugy, not acc
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <algorithm>

struct data { int x, y; };
data operator*(data const& a, int l) { return {a.x * l, a.y * l}; }
data operator+(data const& a, data const& b) { return {a.x + b.x, a.y + b.y}; }
bool operator!=(data const& a, data const& b) { return a.x != b.x || a.y != b.y; }
bool operator==(data const& a, data const& b) { return a.x == b.x && a.y == b.y; }

int const maxn = 5000;
data da[maxn];
int sum[maxn];
int n;

template <class T>
T abs(T x) { return x < 0 ? -x : x; }

int dis(data const& a, data const& b)
{
	return abs(a.x - b.x) + abs(a.y - b.y);
}

int get_id(long long len)
{
	return std::upper_bound(sum + 1, sum + n + 1, len) - sum - 1;
}

data dir(data const& a, data const& b)
{
	if (a.x == b.x) {
		if (b.y > a.y) return {0, 1};
		else return {0, -1};
	} else {
		if (b.x > a.x) return {1, 0};
		else return {-1, 0};
	}
}

using point = data;

bool inrange(int x, int l, int r)
{
	if (l > r) std::swap(l, r);
	return (l <= x) && (x <= r);
}

bool cross(point const& p1, point const& p2, point const& q1, point const& q2)
{
	data d1 = dir(p1, p2);
	data d2 = dir(q1, q2);
	if ((!d1.x && !d2.x) || (!d1.y && !d2.y)) return false;
	if (p1.x == p2.x) {
		if (!(inrange(q1.y, p1.y, p2.y) && inrange(p1.x, q1.x, q2.x))) return false;
		auto l1 = abs(p1.y - q1.y);
		auto l2 = abs(p1.x - q1.x);
		return l1 < l2;
	} else {
		if (!(inrange(p1.y, q1.y, q2.y) && inrange(q1.x, p1.x, p2.x))) return false;
		auto l1 = abs(p1.x - q1.x);
		auto l2 = abs(q1.y - p1.y);
		return l1 < l2;
	}
}

bool judge(long long mid)
{
	int head = get_id(mid), tail = 1;
	int hpos = mid, tpos = 0;
	for (int i = 0; i < n; i++) {
		if (head == n) break;
		int dh = sum[head + 1] - hpos;
		int dt = sum[tail + 1] - tpos;
		if (dh < dt) {
			data ph = da[head] + dir(da[head], da[head + 1]) * (hpos - sum[head]);
			data pt = da[tail] + dir(da[tail], da[tail + 1]) * (tpos - sum[tail]);
			data pt2 = pt + dir(da[tail], da[tail + 1]) * dh;
			if (head != tail + 1 && cross(ph, da[head + 1], pt, pt2)) return false;
			head++; hpos += dh; tpos += dh;
		} else {
			data ph = da[head] + dir(da[head], da[head + 1]) * (hpos - sum[head]);
			data ph2 = ph + dir(da[head], da[head + 1]) * dt;
			data pt = da[tail] + dir(da[tail], da[tail + 1]) * (tpos - sum[tail]);
			if (head != tail + 1 && cross(ph, ph2, pt, da[tail + 1])) return false;
			tail++; hpos += dt; tpos += dt;
			if (dh == dt) head++;
		}
	}
	return true;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> da[i].x >> da[i].y;
		if (i > 1) sum[i] = sum[i - 1] + dis(da[i], da[i - 1]);
	}
	long long l = 0, r = sum[n];
	while (l + 1 < r) {
		auto mid = (l + r) / 2;
		if (judge(mid)) l = mid;
		else r = mid;
	}
//	std::cout << judge(1) << "\n";

	if (judge(r)) l = r;
	std::cout << l << "\n";
}

